"""
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
时间复杂度：Ο(n+k)(其中k是整数的范围)
"""


def count_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    max_num = max(arr)
    count = [0] * (max_num + 1)
    for i in arr:
        count[i] += 1
    result = []
    for i in range(max_num + 1):
        for j in range(count[i]):
            result.append(i)
    return result


if __name__ == '__main__':
    test_arr = [8, 6, 3, 6, 5, 8, 3, 5, 1, 0]
    new_test_arr = count_sort(test_arr)
    print(new_test_arr)
